#!/usr/bin/env python3

"""
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
"""

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def generate_trees(self, n):
        result = []
        for case in self.yield_tree_case(1, n):
            result.append(case)
        return result


    def yield_tree_case(self, start, end):
        if start == end:
            yield TreeNode(start)
            return

        for index in range(start, end + 1):
            for case in self.yield_case(start, end, index):
                result = TreeNode(index)
                result.left = case[0]
                result.right = case[1]
                yield result

    def yield_case(self, start, end, root):
        if root == start:
            for case in self.yield_tree_case(start + 1, end):
                yield (None, case)
        elif root == end:
            for case in self.yield_tree_case(start, end - 1):
                yield (case, None)
        else:
            for left_case in self.yield_tree_case(start, root - 1):
                for right_case in self.yield_tree_case(root + 1, end):
                    yield (left_case, right_case)

            


if __name__ == '__main__':
    s = Solution()
    result = s.generate_trees(3)
    print(f'result: {len(result)}')
